#! /usr/bin/env python3
# -*- coding: utf-8 -*-

"""
双向链表实现
"""


class Node:
    """双向链表节点"""

    def __init__(self, item, next=None, prev=None):
        self.item = item
        self.next = next
        self.prev = prev


class DoubleLinkedList:
    """双向链表"""

    def __init__(self, head=None):
        self.head = head

    def is_empty(self):
        if not self.head:
            return True
        return False

    def length(self):
        """链表长度"""
        # 创建游标
        cur = self.head
        # 计数
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count

    def append(self, item):
        """尾部添加元素"""
        # 实例一个结点
        node = Node(item)
        if self.is_empty():
            self.head = node
            return

        cur = self.head
        while cur.next:
            cur = cur.next

        # 当前结点的next指针指向插入结点
        cur.next = node
        # 插入结点的prev指针指向当前结点
        node.prev = cur

    def add(self, item):
        """向链表头部添加元素"""
        # 实例一个结点
        node = Node(item)
        if self.is_empty():
            self.head = node
            return

        # 当前头结点的prev指针指向新结点
        self.head.prev = node
        # 新结点的next指针指向当前头结点，实现当前头结点后移与新头结点连接
        node.next = self.head
        # 替换链表头结点
        self.head = node

    def insert(self, item, index):
        """向链表指定位置插入元素"""
        if index <= 0:
            self.add(item)
        elif index > self.length() - 1:
            self.append(item)
        else:
            # 实例化结点
            node = Node(item)
            cur = self.head
            conent = 0
            # 遍历找到索引对应的数据
            while conent < index - 1:
                cur = cur.next
                conent += 1

            # 首先需要将前面数据的next指针指向插入数据
            cur.prev.next = node
            # 再将插入数据的prev指针执行前面数据
            node.prev = cur.prev
            # 将当前数据的prev指针指向插入数据
            cur.prev = node
            # 最后插入数据的next指针指向当前数据，实现插入操作
            node.next = cur

    def search(self, item):
        """查询结点"""
        if self.is_empty():
            return False

        # 创建游标
        cur = self.head

        # 记录索引位置
        index = 1
        while cur:
            if cur.item == item:
                return index
            index += 1
            cur = cur.next

    def remove(self, item):
        """删除结点"""
        if self.is_empty():
            return False

        if not self.search(item):
            print("链表中不存在数据：%s" % item)
            return False

        # 创建游标
        cur = self.head
        while cur:
            if item == cur.item:
                # 删除元素是头结点
                if cur == self.head:
                    # 链表只有一个元素
                    if not cur.next:
                        self.head = None
                        return False
                    cur.next.prev = None
                    self.head = cur.next

                # 删除的是尾结点
                elif not cur.next:
                    cur.prev.next = None
                else:
                    cur.next.prev = cur.prev
                    cur.prev.next = cur.next
            cur = cur.next

        return True

    def travel(self):
        """遍历链表"""
        cur = self.head
        # 链表可能是空链表
        if self.is_empty():
            print("该链表为空链表！！！")
            return

        # 获取每个node的数据
        # 移动游标，输出node内的数据
        while cur:
            print(cur.item, end=' ')
            # print(cur.prev, end=' ')
            # print(cur.next, end=' ')
            cur = cur.next
        print()

    def reverse(self):
        """
        双向链表逆序
        """
        cur = self.head
        while cur:
            # 遍历到尾结点时，尾结点设为头结点
            if not cur.next:
                self.head = cur
            # 先临时记录下一个结点
            temp = cur.next
            cur.next = cur.prev
            cur.prev = temp
            cur = temp


if __name__ == '__main__':
    s = DoubleLinkedList()
    s.append(200)
    s.append(100)
    s.append(500)
    s.append(400)
    s.add(300)
    s.add(600)
    # s.travel()
    # print(s.length())
    # s.insert(900, 5)
    # s.remove(900)
    s.travel()
    s.reverse()
    s.travel()
    # print(s.search(100))
